\section{Enunciado}
\parindent = 0 pt
\parskip = 11 pt
\newcommand{\real}{\hbox{\bf R}}

\begin{centering}
\bf Laboratorio de M\'etodos Num\'ericos - Segundo cuatrimestre 2008 \\
\bf Trabajo Pr\'actico N\'umero 3: Autovalores comprimidos \\
\end{centering}

\vskip 25pt
\hrule
\vskip 11pt

El objetivo del trabajo pr\'actico es implementar un m\'etodo para
comprimir im\'agenes en blanco y negro usando la descomposici\'on
en valores singulares de una matriz.

\textbf{El m\'etodo de compresi\'on}

Sea $A\in\real^{n\times m}$ una matriz con los datos de la imagen
en tonos de gris, de manera tal que cada coeficiente $a_{ij}$ es
un n\'umero entre 0 y 255 que indica el nivel de gris del pixel
de la fila $i$ y columna $j$ (si $a_{ij}=0$ entonces el pixel es
negro, y si $a_{ij}=255$ entonces es blanco). La descomposici\'on
en valores singulares de $A$ es la factorizaci\'on
$A\ =\ U \Sigma V^T$, donde $U$ y $V$ son matrices ortonormales y $\Sigma$
es una matriz diagonal. Suponemos adem\'as que las filas y columnas de
estas matrices est\'an ordenadas de modo tal que los elementos
de la diagonal de $\Sigma$ se encuentran de mayor a menor.

Para obtener las matrices $U$ y $V$ de la descomposici\'on
$A = U\Sigma V^T$ podemos utilizar el siguiente m\'etodo: Si
multiplicamos $A = U\Sigma V^T$ por $A^T$ a derecha, tenemos que
$U$ es la matriz de autovectores de la matriz $AA^T$ (por qu\'e?).
Por otra parte, si multiplicamos $A = U\Sigma V^T$ por $A^T$ a
izquierda, tenemos que $V$ es la matriz de autovectores de
la matriz $A^TA$.

Sea $k$ un entero entre 1 y $n$. Llamamos $\tilde{U}\in\real^{n\times k}$
y $\tilde{V}\in\real^{m\times k}$ a las matrices formadas por las primeras
$k$ columnas de $U$ y $V$, respectivamente, y llamamos tambi\'en
$\tilde{\Sigma}\in\real^{k\times k}$ a la matriz formada por las
primeras $k$ filas y $k$ columnas de $\Sigma$. La informaci\'on comprimida
consiste de las matrices $\tilde{U}$ y $\tilde{V}$, junto con la diagonal
de $\tilde{\Sigma}$, y la matriz reconstruida a partir de esta informaci\'on
es $\tilde{A} = \tilde{U} \tilde{\Sigma} \tilde{V}^T$.

\textbf{Enunciado}

Se pide implementar un programa que lea una imagen desde un archivo
y que ejecute este m\'etodo de compresi\'on, dejando la
imagen resultante en otro archivo. El programa debe
tomar como par\'ametros los nombres de los archivos de entrada y
de salida, junto con el porcentaje de filas/columnas a  eliminar
de las matrices de la descomposici\'on en valores singulares de
la imagen original.

El formato de los archivos de entrada y salida queda a
elecci\'on del grupo, aunque sugerimos que utilicen im\'agenes
en formato \textsc{Raw}. El c\'alculo de las matrices
$U$ y $V$ en la descomposici\'on $A = U\Sigma V^T$ se debe
realizar utilizando el m\'etodo QR aplicado a las
matrices $AA^T$ y $A^TA$, respectivamente. Se deben definir
criterios adecuados para detectar la convergencia de este 
m\'etodo en el programa implementado, discutiendo en el 
informe las alternativas consideradas.

\vfil \eject

Sobre la base de la implementaci\'on, se pide medir la 
calidad de la imagen reconstruida en funci\'on de la tasa
de compresi\'on, para analizar el comportamiento del
m\'etodo como he\-rra\-mien\-ta de compresi\'on. Para medir
el error de la imagen resultante, sugerimos utilizar
el \emph{error cuadr\'atico medio}, definido como
\begin{displaymath}
\hbox{ecm}(A,\tilde{A})\ =\ \frac{\sum_{i=1}^n \sum_{j=1}^m (a_{ij} - \tilde{a}_{ij})^2}{nm}.
\end{displaymath}
>Se observan resultados acordes con lo esperado? Analizar cualitativamente
estos resultados, y la calidad visual de las im\'agenes reconstruidas con
tasas de compresi\'on altas. >Qu\'e caracter\'\i sticas tienen estas
im\'agenes?

\textbf{Objetivos adicionales}

Como objetivo adicional, puede ser interesante generar una
animaci\'on de la ``reconstrucci\'on'' progresiva de la imagen, de
manera tal que el $k$-\'esimo cuadro de la animaci\'on sea la imagen
resultante de la reconstrucci\'on utilizando $k$ filas para
la compresi\'on, para $k=1,\dots,n$.

Un segundo objetivo adicional es ejecutar estos experimentos con aritm\'etica
binaria de precisi\'on arbitraria, para analizar el c\'alculo de autovalores
y la calidad de la reconstrucci\'on en funci\'on de la cantidad de bits
en la mantisa de la representaci\'on en punto flotante. >Se observan
diferencias para valores razonables de bits en la mantisa?

\vskip 15pt

\hrule

\vskip 11pt

Fecha de entrega: Lunes 3 de Noviembre

\newpage